package exerise;

/**
 * Created by jimmy on 2019/3/15.
 * 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * <p>
 * 说明：你不能倾斜容器，且 n 的值至少为 2。
 * <p>
 * 输入: [1,8,6,2,5,4,8,3,7]
 * 输出: 49
 */
public class Ex11 {

    public static void main(String[] args) {

        Ex11 ex11 = new Ex11();
        int[] src = {5, 8, 1, 12, 6, 7, 9, 6, 3};
        int result = ex11.maxArea(src);
        System.out.println("result == " + result);
        int result2 = ex11.maxArea2(src);
        System.out.println("result2 == " + result2);

    }

    public int maxArea(int[] height) {
        int area = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int w = j - i;
                int h = Math.min(height[i], height[j]);
                area = Math.max(area, w * h);
            }
        }
        return area;
    }

    public int maxArea2(int[] height) { //[1,2]
        int l = 0;
        int r = height.length - 1;
        int area = 0;
        while (l < r) {
            area = Math.max(area, (r - l) * Math.min(height[l], height[r]));
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return area;
    }
}
